package com.lijing.BackTracing1;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Description 给定两个整数 n 和 k，返回 1 ... n 中所有可能的k个数的组合
 * @title: Combination1
 * @Author LiJing
 * @Date: 2021/4/51:25 下午
 * @Version 1.0
 */
public class Combination1 {
    public static void main(String[] args) {
        int n = 4;
        int k = 3;
        List<Stack<Integer>> result = new ArrayList<>();
        Stack<Integer> path = new Stack<>();
        backTrack(1,n,k,path,result);
        System.out.println(result);
    }

    
    public static void backTrack(int startIndex, int n, int k, Stack<Integer> path, List<Stack<Integer>> reuslt){
        if (path.size() == k){
            reuslt.add((Stack<Integer>)path.clone());
            return;
        }

        //选择：本层集合中的元素，树中节点孩子的数量就是集合的大小
        for (int i = startIndex; i <= n-(k-path.size())+1; i++) {
            //处理节点
            path.push(i);
            //递归
            backTrack(i+1,n,k,path,reuslt);
            //回溯，撤销处理结果
            path.pop();
        }
    }


}
